Optimal Deterministic Broadcasting in Known Topology Radio Networks

We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length , for every n-node graph of diameter D, thus improving a result of Gąsieniec et al. (PODC 2005) [17] and solving a problem stated there. Unless the inclusion NP BPTIME( holds, the length of a polynomially constructible deterministic broadcast scheme is optimal.A preliminary version of this paper (with a weaker result) appeared in the Proc. 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’2004), August 2004, Harvard University, Cambridge, USA, LNCS 3122, 171–182. Research of the second author supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais. Part of this work was done during the second author’s visit at the Max-Planck-Institut für Informatik.     

Robust gossiping with an application to consensus

We study deterministic gossiping in synchronous systems with dynamic crash failures. Each processor is initialized with an input value called rumor. In the standard gossip problem, the goal of every processor is to learn all the rumors. When processors may crash, then this goal needs to be revised, since it is possible, at a point in an execution, that certain rumors are known only to processors that have already crashed. We define gossiping to be completed, for a system with crashes, when every processor knows either the rumor of processor v or that v has already crashed, for any processor v. We design gossiping algorithms that are efficient with respect to both time and communication. Let t<n be the number of failures, where n is the number of processors. If , then one of our algorithms completes gossiping in O(log²t) time and with O(npolylogn) messages. We develop an algorithm that performs gossiping with O(n^1.77) messages and in O(log²n) time, in any execution in which at least one processor remains non-faulty. We show a trade-off between time and communication in gossiping algorithms: if the number of messages is at most O(npolylogn), then the time has to be at least . By way of application, we show that if n−t=Ω(n), then consensus can be solved in O(t) time and with O(nlog²t) messages.     

An efficient algorithm for finding ideal schedules

We study the problem of scheduling unit execution time jobs with release dates and precedence constraints on two identical processors. We say that a schedule is ideal if it minimizes both maximum and total completion time simultaneously. We give an instance of the problem where the min-max completion time is exceeded in every preemptive schedule that minimizes total completion time for that instance, even if the precedence constraints form an intree. This proves that ideal schedules do not exist in general when preemptions are allowed. On the other hand, we prove that, when preemptions are not allowed, then ideal schedules do exist for general precedence constraints, and we provide an algorithm for finding ideal schedules in O(n ³) time, where n is the number of jobs. In finding such ideal schedules we resolve a conjecture of Baptiste and Timkovsky (Math. Methods Oper. Res. 60(1):145–153, 2004) Further, our algorithm for finding min-max completion-time schedules requires only O(n ³) time, while the most efficient solution to date has required O(n ⁹) time.     

Agent-based guided local search

The main contribution of the paper is to propose and validate a new hybrid approach for solving combinatorial optimization problems in which guided local search metaheuristic is incorporated into a cooperative multi-agent framework based on the concept of asynchronous teams (A-Teams). Generally, an A-Team assumes that a collection of software agents, each representing a particular problem solving method, cooperate to solve a problem by dynamically evolving a population of solutions. In the suggested implementation each software agent carries out a guided local search. The proposed approach has been extensively validated experimentally on one of the best known combinatorial optimization problem – the vehicle routing problem. The promising results of experiments have confirmed the effectiveness of the suggested approach.     

On some properties of Goursat–Darboux systems with distributed and boundary controls

In this paper, a Goursat–Darboux control system is considered. In the first part, the bang-bang principle and some approximation results concerning the piecewise constant controls, for a linear system with distributed and boundary controls, are proved. In the second part, an approximation result concerning the bang-bang controls, for a special case of nonlinear (in a state) system with distributed controls, is derived.     

Existence of optimal solutions of two-directionally continuous linear repetitive processes

In the paper, an existence theorem for a Lagrange optimal control problem connected with a two-directionally continuous variant of a linear autonomous repetitive process is derived. As a corollary, existence of an optimal solution in the case of cost functional depending on a fixed ??end-function?? is obtained.     

Performance indices of a common rail-system CI engine powered by diesel oil and biofuel blends

Conventional fuels used for supplying internal combustion piston engines include petrols and diesel oils produced from petroleum. These are a non-renewable energy source. The environmental policy of the European Union is geared towards increasing the share of renewable fuels in the overall energy consumption. An alternative fuel originating from a renewable source, which could be used for feeding self-ignition internal combustion engines are the fatty acid methyl esters (FAME) of plant oils. The paper reports selected results of testing a 1.3 MULTIJET SDE 90 PS self-ignition engine with the Common Rail reservoir feed system supplied with mixtures of diesel oil and rape oil fatty acid methyl esters (FAME). Tests were carried out on an engine test bed equipped with an eddy-current brake. The purpose of the tests was to determine the economic–energy and ecological indices of engine operation. The concentrations of exhaust gas gaseous components were measured using a MEXA-1600DEGR analyzer, while the particulate concentrations, with a MEXA-1230PM analyzer. In addition, the variations of working medium pressures in the engine chamber and of fuel pressure upstream the injector were recorded as a function of crankshaft rotation angle using the AVL IndiSmart 612 indication system for this purpose. The physicochemical properties of fuels used in the tests were determined using a fuel analyzer. The obtained testing results made it possible to determine and assess the operation indices of the engine fed with mixtures of diesel oil and rape oil fatty acid methyl esters (FAME) with slightly higher ester contents than the requirements of the currently applicable diesel oil standard.